package gold.gold03;

import java.util.*;

/**
 *
 * 我们一个个地添加括号, 每次添加括号, 新增的括号里面必然是合法的内容。
 * 所以新增第n个括号时, 选择括住0~n-1个括号, 然后循环就行了。注意这个方法没有办法处理重复情况, 手动去重。
 * 用Set去重。
 */
public class S0809括号的所有合法组合 {
    /**
     * 10, 先把所有的创建出来, 再判断是否合法。有点耗时。
     */
    public List<String> generateParenthesis(int n) {
        // List<char[]> allRes = new ArrayList<>();
        Set<String> allResSet = new HashSet<>();


        char[] initChar = new char[2*n];
        // 这里的填充, 以及下面的set->list的转换, 优化。
//        for(int i = 0; i < initChar.length; i++){
//            initChar[i] = '(';
//        }
        Arrays.fill(initChar, '(');
        generateAll(allResSet, initChar, 0);
//        List<String> res = new ArrayList<>();
//        for(String s: allResSet){
//            res.add(s);
//        }
        return new ArrayList<>(allResSet);
    }

    public void generateAll(Set<String> allRes, char[] curChar, int loc){
        if(loc >= curChar.length) return;

        curChar[loc] = '(';
        // 注意这里allRes不能是Set<char[]>, 然后每次添加curChar进去,
        // 因为这样每次添加一个char[], 这是个引用变量, 后面改了之后, 把前面的全都改了, 所以一定要添加新的变量。
        if(isValid(curChar)) allRes.add(new String(curChar));
        generateAll(allRes, curChar, loc+1);

        curChar[loc] = ')';
        if(isValid(curChar)){
            allRes.add(new String(curChar));
            //System.out.println(curChar);
        }
        generateAll(allRes, curChar, loc+1);

    }
    public boolean isValid(char[] curChar){
        int count = 0;
        for(char c: curChar){
            if(c == '('){
                count ++;
            }else{
                count --;
                if(count < 0) return false;
            }
        }
        return count == 0;
    }

    /**
     * 100, 看了别人的思路, 我试一下回溯, 果然可以。
     * 总之就是注意一下左右括号的选择条件以及中止条件吧。
     * 我觉得条件的判断还有一定优化空间, 我使用char[] 而不是String的拼接, 感觉对java来说这点内存完全随机。
     */
    public List<String> generateParenthesis2(int n) {
        List<String> res = new ArrayList<>();
        char[] tempCharArray = new char[n*2];
        addString(res, tempCharArray, 0, 0, 0);
        return res;
    }
    public void addString(List<String> res, char[] tempCharArray, int loc, int leftNum, int rightNum){
        int totalNum = (int)tempCharArray.length/2;
        // if(leftNum == totalNum && rightNum == totalNum) return;
        if(loc == 2*totalNum){
            res.add(new String(tempCharArray));
            return;
        }
        if(totalNum > leftNum){
            // 只要左括号还有, 就可以用
            tempCharArray[loc] = '(';
            addString(res, tempCharArray, loc + 1, leftNum + 1, rightNum);
            // 左括号还有, 一定条件下也可以用右括号
            if(leftNum > rightNum){
                tempCharArray[loc] = ')';
                addString(res, tempCharArray, loc + 1, leftNum, rightNum + 1);
            }
        }else{
            // 左括号没了
            tempCharArray[loc] = ')';
            addString(res, tempCharArray, loc + 1, leftNum, rightNum + 1);
        }


    }

}
